UVa/562 - Dividing coins/robado1.cpp

   1 //Robado de: http://www.wretch.cc/blog/celiaailec/19569472
   2 //  Q562: Dividing coins
   3 //  2008.05.29     Celia
   4 //  Method: Dynamic Programming
   5 //  Result: Accepted
   6 //  Time: 0.050
   7 #include <stdio.h>
   8 #include <string.h>
   9
  10 #define N 101
  11 #define M 25001
  12
  13 bool v[M];
  14
  15 int iabs(int n)
  16 {
  17     return (n > 0)? n : -n;
  18 }
  19
  20 int main()
  21 {
  22     int i, j, t, n, m, sum, a[N];
  23     scanf("%d", &t);
  24
  25     while(t-- > 0)
  26     {
  27         scanf("%d", &n);
  28
  29         for(sum = 0, i = 1; i <= n; i++)
  30             scanf("%d", &a[i]), sum += a[i];
  31
  32         m = sum / 2;
  33         memset(v, 0, sizeof(v));
  34         v[0] = true;
  35
  36         for(i = 1; i <= n; i++)
  37             for(j = m; j >= 1; j--)
  38                 if(!v[j])
  39                     v[j] = (a[i] <= j)? v[j-a[i]] : false;
  40
  41         for(j = m; j >= 1; j--)
  42             if(v[j])
  43                 break;
  44
  45         printf("%d\n", iabs(sum - j * 2));
  46     }
  47
  48     return 0;
  49 }